%\section{Related Work}
\label{ch:related}

In this Chapter, the existing research work in related areas is reviewed. Section ~\ref{sec:actors} presents the Actor model for object-oriented concurrency, which has been used in this work. Actors offer a natural programming framework for implementation of open distributed systems. In Section ~\ref{sec:actorimp}, a number of Actor implementations are reviewed. Section ~\ref{sec:cyberorg2} introduces the CyberOrgs, a model that provides mechanisms for coordinating resources among self-interested peers. Section ~\ref{sec:spatialscaling} summarizes related work in spatial distribution of game space to build scalable multiplayer games. Works related to genre specific limitations of MMOGs are presented in Section ~\ref{sec:genrelimit}. In Section ~\ref{sec:dynresprov}, research related to crowding and different resource provisioning approaches to deal with crowding are reviewed.

\section{Actors}
\label{sec:actors}
The concept of Actors was first introduced by Hewitt \cite{Hewitt_Robot} in his work for PLANNER, a language for proving theorems in Robots. Later, Hewitt \emph{et al.} formalized the Actor model in \cite{Hewitt_AI, Hewitt_MP}. His work was carried on by Grief, who developed an abstract model for actors \cite{Grief} and Clinger, who developed the semantics for actors \cite{Clinger}. Afterwards, Agha extended actors to programming languages \cite{Agha_A, Agha_AC}. He is also the pioneer in modelling Actors for data abstraction \cite{Agha_Abstraction} in open distributed systems.

\begin{figure}
\centering
\includegraphics[scale=0.55]{actor}
\caption{Structure of an actor.}
\label{fig:actor}
\end{figure}

Figure ~\ref{fig:actor} shows the structure of an actor. Actors are autonomous computational entities. An actor consists of a state, set of behaviours (methods) and a thread of control. Actors communicate with each other using asynchronous, point-to-point messages. Each actor has a globally unique name, which is used by other Actors to send messages. As Actors represent computations they can be distributed over time and space. In other words, it is possible to enable an actor for a specific time at a specific location. Actors store unprocessed messages in a queue and process them one by one according to the order of arrival. The processing of messages, however, solely depends on the scheduling strategy implemented in the underlying Actor System. Three types of \emph{actor primitives }may occur during the processing of a message:

\begin{itemize}
\item An actor can send messages to another actor. The name of the destination actor must be known to the sender actor. The messages sent by Actors are guaranteed to eventually be delivered to the destination actors, but the order of arrival is not guaranteed.
\item New actors can be created with predefined characteristics. The creator actor knows the name of the newly created actor.
\item An actor can change its own state.
\end{itemize}

\section{Actor Implementations}
\label{sec:actorimp}
There are several implementations of Actors. In this section, we review some of the existing Actor Systems:  \emph{Actor Architecture} \cite{Actor_Architecture}
, \emph{Actor Foundry} \cite{Actor_Foundry} and \emph{SALSA}.\footnote{http://www.cs.rpi.edu/research/groups/wwc/salsa/index.html}

\subsection{Actor Architecture}

Actor Architecture is an actor-based framework implemented in Java. Actor Architecture consists of AA platforms that provide execution environments for actors as well as API support to develop actors. These platforms also allow Actors across distributed systems to execute and communicate with each other through message passing. Each AA platform consists of four service layers:

\begin{itemize}

\item{\emph{Actor Management Service:}}\\
The Actor Management Service layer manages the states of the actors and manages all the migrations between the AA platforms.
\item{\emph{Message Delivery Service:}}\\
The Message Delivery Service layer handles transportation of all the local messages in the AA platform.
\item {\emph{Message Transport Service:}}\\
The Message Transport Service layer provides an interface to communicate between actors of other AA platforms. All messages that are sent to or received from another AA platform pass
through the Message Transport Service layer.
\item{\emph{Advanced Service:}}\\
The Advanced Service layer provides middleware services, such as matchmaking and brokering, which facilitates look up services to search for a particular actor.
\end{itemize}

The distributed resource management system that is presented in this thesis has been developed by extending Actor Architecture and the CyberOrgs model. The CyberOrgs \cite{cyber} model, discussed in Section 2.3 is developed using Actor Architecture. 

\subsection{Actor Foundry}

Actor Foundry is another implementation of Actor model developed using Java. Each instance of the Actor Foundry run-time system is called a foundry node. Each foundry node can employ many actor instances and these actors may communicate with each other using asynchronous messages. The message delivery in Actor Foundry is weakly fair; that is, messages are guaranteed to be delivered eventually at the destination. Like Actor Architecture, Actor Foundry also allows programmers to define behaviour of actors through the programming interface provided.

\begin{figure}
\centering
\includegraphics[scale=0.55]{actorfoundry}
\caption{Actor Foundry Node Structure \cite {Mark_afman}.}
\label{fig:actorfoundry}
\end{figure}

Figure ~\ref{fig:actorfoundry} shows the structure of a foundry node. As we can see from the figure, each foundry node consists of seven basic components:

\begin{itemize}
\item{\emph{Actor Manager:}}\\
The Actor Manager carries out the operations required for actor creation and begin scheduling. It is also responsible for all intra-node communication and carries out requests from other actors to the request handler. 
\item{\emph{Actor Implementation:}}\\
Each actor instance is represented by an Actor Implementation. It transfers messages to the Actor Manager, which handles local communication inside a node.

\item{\emph{Service:}}\\
The Service Modules provide additional platform specific services to the local actors. Actors communicate with the Actor Manager to access these services.


\item{\emph{Request Handler:}}\\
The Request Handler module bridges a local Actor Manager to another Actor Manager on a different foundry node. It provides an interface to communicate other Actor Managers through synchronous or asynchronous remote procedure calls (RPCs). The low-level detail of the message transport services is encapsulated by the Transport Layer. The request handler also provides Name Service to identify an Actor.
\item{\emph{Name Service:}}\\
Each actor in the Actor Foundry is given an unique name. This name is generated by the Name Service module. Request Handler, using this module can setup appropriate Remote Procedure Calls.
\item{\emph{Transport Layer:}}\\
The Transport Layer deals with the low-level communication protocols. Messages of any size are guaranteed to be transported eventually.
\item{\emph{Scheduler:}}\\
The Scheduler module schedules all the threads in a foundry node. Actor Foundry employs fair scheduling strategies.
\end{itemize}

\subsection{SALSA}
Simple Actor Language System and Architecture (SALSA) is an actor-based programming language designed for developing dynamically reconfigurable open distributed applications.
SALSA supports all basic actor primitives such as asynchronous message passing, unbounded concurrency and state encapsulation. Additionally, SALSA provides universal naming, remote communication and migration services to support distributed computing over the Internet \cite{Varela_SALSA}. Furthermore, SALSA provides high-level abstractions such as token passing, join and first-class continuations to facilitate concurrent operations.

SALSA syntax is very similar to Java. SALSA compiler translates a SALSA source code to a Java source and then Java compiler produces the final Java byte-code. This facilitates portability across various Java-supported platforms.


\section{CyberOrgs}
\label{sec:cyberorg2} 

The CyberOrgs model \cite{Cyber_Jamali}, introduced by Jamali \emph{et al.} is a model for hierarchical resource coordination between multiple self-interested peers over a network of peer-owned resources. A cyberorg encapsulates an amount of resource as well as a set of computations executed by concurrent actors. Additionally, a cyberorg can host another cyberorg and there exists a contractual relationship between the child cyberorg and the parent cyberorg, potentially the host of a child cyberorg. The resource required by a concurrent activity, executed by an actor is allocated by the containing cyberorg.  The contractual relationship between cyberorgs is analogous to a buyer-seller relationship. The virtual currency that flows among cyberorgs is called \emph{eCash}. 

\begin{figure}
\centering
\includegraphics[scale=0.45]{cyberorg}
\caption{Structure of a cyberorg.}
\label{fig:cyberorg}
\end{figure}

Figure ~\ref{fig:cyberorg} shows the structure of a cyberorg. In this figure, each ellipse represents a cyberorg and each curved line represents a computation. Each cyberorg contains actors, eCash, messages and may contain one or more cyberorgs. In this model, actors represent computations and a cyberorg can use its eCash to buy resources required for these computations. Actors in the cyberorg communicate using asynchronous message passing. A cyberorg organizes its resources and computations in a hierarchical fashion.  A cyberorg can purchase additional resources from another cyberorg according to a contract. This contract is made through a successful negotiation between these two cyberorgs. The contract specifies the types and quantities of resources that will be delivered to the hosted cyberorg. The cost of the resources is also  specified in the contract. A cyberorg distributes its resources among the hosted cyberorgs and the local computations according to its own local resource distribution policy.

The CyberOrgs model defines resources (computational and communication for example) in terms of time and space. A resource expires at a particular point in time at a particular location; if it is not used by some computation. In the CyberOrgs, ticks are defined as the unit of consumable resource and defined in time and space. For example- a resource R at location L has N ticks available from time T1 to time T2. Every computation requires a certain number of ticks to complete.
\\
\\
\textbf{CyberOrgs Primitives}\\

In the CyberOrgs model, three primitive operations are defined. 

\begin{itemize}
\item \emph{Isolation:} A cyberorg can create a new cyberorg by using Isolate primitive. This mechanism allows a cyberorg to collect some of its actors, eCash and allows this new cyberorg to be hosted locally. A contract is also formed between the host cyberorg and the newly created one.

\item \emph{Assimilation:} Using Assimilate primitive a cyberorg can relinquish all of its computations, resources, eCash and control to its host cyberorg and disappear.

\begin{figure}
\centering
\includegraphics[scale=0.45]{isoass}
\caption{Isolation and Assimilation.}
\label{fig:isoass}
\end{figure}

Figure ~\ref{fig:isoass} shows the \emph{isolation} and \emph{assimilation} operation.

\item \emph{Migration:} Migration is a little more complex than the two other primitives and plays a very important role in the CyberOrgs model. A cyberorg may realize that its resource requirement has exceeded according to the contract. If the cyberorg requiring resources has enough eCash, it attempts to migrate to another cyberorg where it can buy more resources and process its computations. Before migration, a cyberorg searches for potential hosts that have enough resources available for purchase. Each migration is initiated with a contract between two cyberorgs. A cyberorg that requires resources for the computations it holds can offer other cyberorgs to trade resources for eCash. Both cyberorgs can negotiate about the terms of the contract. When the negotiation is successful and a contract is signed, the new host allows the other cyberorg to migrate and use its resources.

\begin{figure}
\centering
\includegraphics[scale=0.45]{migrate}
\caption{Migration.}
\label{fig:migrate}
\end{figure}

As shown in Figure ~\ref{fig:migrate}, cyberorg C3, hosted by cyberorg C2 migrates to cyberorg C1 after a successful negotiation.
\end{itemize}

\section{Spatial Scaling of MMOG}
\label{sec:spatialscaling}
This section reviews some of the ideas that are already being used in some MMOGs. In Subsection 2.4.1, three different techniques for spatial scaling are discussed: \emph{zoning}, \emph{mirroring} and \emph{instancing}. Additionally, works related to these techniques are also reviewed. In Subsection 2.4.2, area-of-interest (AOI), a concept being used heavily in MMOGs to reduce communication burden is discussed. This subsection also presents some strategies that facilitate seamless zonal migration.

\begin{figure}
\centering
\includegraphics[scale=0.55]{zone.jpg}
\caption{Zoning and Mirroring.}
\label{fig:zone}
\end{figure}

\subsection{Zoning, Mirroring and Instancing}
Zoning \cite{Cai_zoning_arch} technique used in many games, is based on concepts from data locality in scientific parallel processing. Zones are created to partition the game world into smaller areas. Each zone is handled by a separate host/server. The host is responsible for processing all interactions and requests from the clients that reside in the respective zone. Depending on the implementation of the game, hosts can communicate with each other to share updates and may allow players to migrate form one zone to another. However, this approach alone does not offer much flexibility and scalability in game design nor does it provide any fine-grained control over the resources. Zoning is currently being used in some online adventure games, namely MMORPGs \cite{Assiotis_distributed_arch}. 

Another technique called mirroring \cite{Muller_Rokkatan} is used for parallelizing game sessions for densely populated zones and allows users to see only the objects within their area-of-interest. These densely populated areas are also referred as hotspots \cite{rp}. This novel approach provides distribution of load by replicating the same game zone over multiple hosts. Each host processes a set of entities called active entities for that host. Other entities that are not processed are called shadow entities. Shadow entities are processed in another host where they are considered as active entities. This approach highly scales because the amount of resource required for data transfer as well as computation for an update of a shadow entity is much less than that of transferring and computing the whole game state. Figure ~\ref{fig:zone} shows how zoning and mirroring are used. In the right figure, dark characters represent active entities and grey characters represent shadow entities.

Instancing \cite{Mauve_generic} offers another approach to scale a multiplayer game by distributing the load by creating multiple independent instances of the same zone. Sub-areas that have a very high frequency of access are considered for  instancing. Each host responsible for processing a sub-area is called an instance server. The difference between mirroring and instancing is that each instance server processes entities completely independent of each other. %Figure x shows how instancing can be used.

 Based on these three techniques, Real-Time Framework (RTF) \cite{rtf}, a Grid-based middleware is developed to scale game sessions. RTF is a multilayered service-oriented architecture that uses the potential of grid computing to provide access to unbounded amount of resources. Based on RTF, a model for computing load for MMOGs is developed \cite{rp}. This model also offers opportunities to predict load in advance and necessary steps can be taken to balance the load by real time provisioning of resources. Another load balancing approach is proposed by utilizing the semantics of the simulation executed by the server \cite{lb}. In \cite{rp-4}, a communication architecture is developed for Networked Virtual Environments that takes advantage of unstructured peer-to-peer (P2P) overlay networks for the distribution of messages.

Some of the above ideas are employed in some MMORPGs. However, MMORPG is a specific genre that allows a slow-paced gaming experience than other online genres like First Person Shooter (FPS) games. A highly interactive, fast-paced game requires a lot more processing to update a player's state than any MMORPG. Also there are no approaches developed yet to provide fine-grained control over the resources for the gamer community. Motivated by above approaches and CyberOrg model, this thesis aims to build a scalable online gaming framework with more fine-grained control over the resources and more flexibility in acquiring resources.

\subsection{Interest Management and Zonal Migration}
Scalability is a critical issue when developing MMOGs or multi-user simulation environments. In most modern MMOGs, scalability is achieved through interest management; in other words by dividing the virtual world into smaller areas or zones where each zone is managed by one server \cite{Dewan}. However, due to the unpredictable nature of hotspot creation in a zone, the zoning approach, alone does not always offer the performance and scalability as required. Besides, a static distribution of these areas makes it hard for clients to migrate from one region to another. In some games, this is done using portals. Portals are gateways used to transport a player from one region to another and manages the lag by presenting the user a loading screen or special effect that does not necessarily require any interaction with the server. However, this is not often the case for most games and many developers might want to avoid this kind of solution. This approach provides a discrete view to the users as they can not see objects beyond the zonal  boundaries. Some MMOGs might need a vast open world without these gateways and require to migrate a gamer from one zone to another seamlessly. 

In \cite{Lu}, Lu \emph{et al.} presented a model that facilitates communication among players based on the player behaviour and interactions. In this paper, the author defined the concept of aura, an area enclosed by a sphere for interest management. This behavioural modelling is dynamic in nature and is based on the altitude and viewer range of view. In a nutshell, this model only enables the server to deal with the entities that are in the view radius of the player. Knutsson \emph{et al}.'s P2P Support for Massively Multiplayer Games \cite{Knutsson} and Iimura \emph{et al.}'s Zoned Federation of Games Servers \cite{Iimura} proposed a discrete view of the zones; all computation in a zone is handled by a server and has a discrete view of the world. 

Figure ~\ref{fig:hexzone} shows distribution of game space into several hexagonal shaped zones. How an entity moves from one zone to another is illustrated by Figure ~\ref{fig:zonemigr}.  These approaches independently might provide some level of scalability. However, to offer a gamer with the seamless experience of a huge virtual world, a different approach to zonal migration is required. This thesis investigates these approaches, adopts some of these ideas and combines them to offer a continuous seamless experience to the gamer community without compromising game performance and scalability. 

\begin{figure}
  %\centering
  \subfloat[Distribution of computation among zones]{\label{fig:hexzone}\includegraphics[width=0.7\textwidth]{migration}}  
  \vspace{20mm}        
  \subfloat[Migration of an entity from A to B]{\label{fig:zonemigr}\includegraphics[width=0.65\textwidth]{migration2}}
  \caption{Zonal migration}
  \label{fig:zonalmigration}
\end{figure}

\section{Genre specific limitations}
\label{sec:genrelimit}

Most studies and experimental works so far have focused on the design aspects limited to a special category of games, role-playing-games (RPGs) \cite{rtf}. The other online genres like first-person-shooter (FPS) do not allow ``massive'' number of players to play at the same time. This could be due to the higher interactivity and fast-paced game-play of an FPS than that of an RPG.

A study by Abdelkhalek \emph{et al.} \cite{abdul} showed some interesting analysis and presented some attempts to improve the number of concurrent players in Quake 2, an online FPS game. Quake 2 is an open source 3D first person shooter game developed and distributed by \textit{id software}.\footnote{http://www.idsoftware.com/} Quake multiplayer mode follows client-server architecture. All physics simulations, updating state inconsistencies originated from network delays, hardware issues as well as propagation of updated states to clients are handled by a single, centralized server. The first version of Quake allows 32 players to play simultaneously. This study was able to increase the player limit from 32 to 90 simultaneous players. Their experiment concluded that the bottleneck is caused by the lack of CPU resource rather than network bandwidth. In most cases, incoming bandwidth is constant and low. Some parallelization methods were implemented using task decomposition and synchronization techniques to increase the number of simultaneous players.

\begin{figure}
  %\centering
  \subfloat[Screenshot taken from Halflife 2 (non-MMO).]{\label{fig:nonmmo}\includegraphics[width=0.5\textwidth]{halflife2.jpg}}  
  \hspace{3mm}        
  \subfloat[Screenshot taken from WoW Cataclysm (MMORPG).]{\label{fig:mmo}\includegraphics[width=0.5\textwidth]{wow.jpg}}
  \caption{Screenshots of non-MMO and MMO}
  \label{fig:MMOG}
\end{figure}

However, there has not been any significant research in improving the scalability of FPS games. Recent online games like Counter Strike, Half-Life 2 or Battlefield 1942 do not allow more than few tens of players. Another FPS, Battlefield: \emph{Bad Company} (2008) supports up to 24 simultaneous players \footnote{http://badcompany.ea.com/about/}. Figure ~\ref{fig:MMOG} presents screenshots of an online FPS, Halflife 2 and an MMORPG titled WoW Cataclysm. It is noticeable from the screenshots, that the FPS graphics is much more detail than MMORPG one. In this thesis, this question is addressed in terms of resource coordination and sharing. Novel approaches for resource encapsulation, coordination and sharing for MMOGs are developed. This allows a developer to build online games with potentially unbounded resources, of course, as long as the developer pays and thus, can meet the desired QoS and scalability requirement.

\section{Dynamic Resource Provisioning}
\label{sec:dynresprov}

This section reviews load variability and approaches that can be used to balance the consequences on resource usage. Subsection ~\ref{subsec:2hot} discusses how hotspots are created and their behaviour. In Subsection ~\ref{subsec:2dynamic}, different approaches to model loads and some strategies to provision resources dynamically are presented.
\subsection{Hotspots}
\label{subsec:2hot}
Crowding happens when many players move in to the same zone. As each zone has limited resources, it makes the game server perform poorly if the population gets too high for the server to handle. Crowding violates the quality of service and affects gaming performance. The simple distribution model of resources among zones may not work when crowding happens. Therefore, only even distribution of resources among zones may not be the best approach for balancing the load. In most cases, the population distribution caused by crowding is very random in nature and can not be predicted in advance. 
%Figure x shows a typical crowding scenario.

In \cite{Chen}, Chen \emph{et al.} pointed out that when many players move into the same zone, the result is ``flocking'', an MMOG pattern that can not be ignored. The reason behind this could be the zone is more interesting for its rich content. Some games like real-time strategy games and war games may be scheduled for special battles at specific times. Moreover, people are more likely to play at their leisure time. Therefore, games could be less overloaded during work hours and more overloaded during weekends and times when people do not work. Obviously, this also depends on the timezones and the number of players from those timezones as well.


\subsection{Dynamic load balancing}
\label{subsec:2dynamic}
To deal with transient crowding problem Chen \emph{et al.} proposed a locality aware dynamic partitioning algorithm. This, decentralized algorithm is based on a heuristic approach that allows  the game to i) shed load from an overloaded host considering the locality of the game-entities and ii) merge hosts in normal load condition for reducing excessive inter-server communication due to the partitioning of the hosts. Load shedding is constrained by achieving the safe load target without exceeding the safe load threshold on any nodes to which the overloaded node sheds load. This approach is also aimed at preserving the locality, i.e., the number of strongly connected components must have to be same as before load shedding. Additionally, this strategy also has an optimization goal to keep the number of region migrations incurred due to load shedding minimal.  

Another part of Chen \emph{et al}'s work was to aggregate hosts when the quality of service degrades due to excessive inter-server communication instead of high client load. They presented a heuristic graph merging algorithm to merge servers and improve the quality of service.

According to Nae \emph{et al.} \cite{Nae_drp, rp}, current MMOG industry practice is to over-provision resources due to the high variability of resource demand and lack of flexibility in resource renting policies from third parties. This kind of over-provisioning of resources only enables the big companies to enter the MMOG industry. They addressed the issue of high entry and operational costs and proposed a new dynamic resource provisioning method for MMOGs using third party data centers to enable the developers a low cost solution. In this study, Nae \emph{et al.} attempted to identify the type of interactions that cause short-term load variability, which complements the long-term load variability because of the population increase. Based on the player interaction type and the size of the population, a combined processor, network and memory model is presented. This model estimates the MMOG resource demands dynamically and thus, provides opportunities for dynamic resource provisioning.

\section{Chapter Summary}
In this chapter, work in several related areas is reviewed including the CyberOrgs, a model for resource coordination along with Actor Systems and some actor implementations.  Some resource distribution approaches such as zoning, mirroring and instancing are briefly discussed. Zonal migration, genre specific limitations as well as load variability issues are addressed as resource coordination problems.  
